package xyz.scootaloo.oj.offer

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 22:36
 */
class P39 {

    private fun majorityElement(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]

        val size = nums.size
        var count = 1
        var current = nums[0]

        for (idx in 1 until size) {
            if (nums[idx] == current) {
                count++
            } else {
                count--
                if (count == 0) {
                    current = nums[idx]
                    count = 1
                }
            }
        }

        return current
    }

    @Test
    fun test0() {
        val input = intArrayOf(1, 2, 3, 2, 2, 2, 5, 4, 2)
        println(majorityElement(input))
    }

}
